public class Test08 {
    public static void main(String[] args) {
        // 典型输入，单调升序的数组的一个旋转
        int[] array1 = {3, 4, 5, 1, 2};
        System.out.println(getmin(array1));

        // 有重复数字，并且重复的数字刚好的最小的数字
        int[] array2 = {3, 4, 5, 1, 1, 2};
        System.out.println(getmin(array2));

        // 有重复数字，但重复的数字不是第一个数字和最后一个数字
        int[] array3 = {3, 4, 5, 1, 2, 2};
        System.out.println(getmin(array3));

        // 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字
        int[] array4 = {1, 0, 1, 1, 1};
        System.out.println(getmin(array4));

        // 单调升序数组，旋转0个元素，也就是单调升序数组本身
        int[] array5 = {1, 2, 3, 4, 5};
        System.out.println(getmin(array5));

        // 数组中只有一个数字
        int[] array6 = {2};
        System.out.println(getmin(array6));

        // 数组中数字都相同
        int[] array7 = {1, 1, 1, 1, 1, 1, 1};
        System.out.println(getmin(array7));
        System.out.println(getmin(array6));

        // 输入NULL
        System.out.println(getmin(null));

    }
    public static int getmin(int[] nums){
        if (nums == null || nums.length == 0) throw new RuntimeException("Invalid");
        int start = 0;
        int end = nums.length-1;
        int mid = start;
        while (nums[start] >= nums[end]){
            if(end - start == 1) return nums[end];
            mid = (end-start)/2+start;
            if(nums[mid] == nums[start] && nums[end] == nums[mid]) return minInorder(nums,start,end);
            else if(nums[mid] >= nums[start]) start = mid;
            else if(nums[mid] <= nums[end]) end = mid;
        }
        return nums[mid];
    }

    public static int minInorder(int[] nums,int start,int end){
        int res = nums[start];
        for(int i =  start+1;i<= end;i++){
            if(res > nums[i]) res = nums[i];
        }
        return res;
    }
}
